/*
	求和运算
*/

#include <stdio.h>

struct res{
		int n;
		int sum;
	};
struct res arr[1024];

int main (){
	int i = 0;
	int sum = 0;
	int n = 10;
	//算法一：
	while(1){
		printf("请输入一个值：\n");
		scanf("%*c");
		scanf("%d",&n);
		//判断n对应的累加和是否计算过
		int j = 0;
		for(j = 0;j < 1024;j++){
				if(arr[j].n == n) {
					sum = arr[j].sum; 
					break;
					}
			}
		if(j == 1024){
		for(i = 0;i < n;i++){
			sum += i;//时间复杂度O(n)
		}
		int m = 0;
		for(m = 0; m < 1024; m++){
			if(arr[m].n == 0){
				break;
				}
			}
		arr[m].n = n;
		arr[m].sum = sum;
		}
		printf("sum = %d\n",sum);
	}


#if 0
	//算法二：
	sum = (1 + n) * n / 2;//时间复杂度O(1)
	printf("sum = %d\n",sum);
#endif				
	}

